#!/usr/bin/env python
#coding:utf-8

import os
import math

def input_mountain_value():
	while True:
		print '输入山峰坐标，用","分割：',
		input_para = raw_input()
		rtn, mountain_array = check_input_para(input_para)
		if False == rtn:
			print '输入坐标值无效，请重新输入！'
			continue
		else:
			return mountain_array


# 检查输入值，并转换为数字数组
def check_input_para(input_para):
	mountain = input_para.replace(' ', ',').split(',')

	for idx, val in enumerate(mountain):
		if not val.isdigit():
			return False, None
		else:
			mountain[idx] = int(val)

	return True, mountain

'''
	思路:
	1、先找到有效的山峰（从第一个山峰作为有效山峰，只要后边的山峰不小于当前值，则它也是有效山峰，然后再用新的有效山峰做基准继续查找）
	2、这样查找，会导致最高山峰后续的山峰都被抛弃了，所以还需要从右往左在查找一次，取两次查找的交集
	3、为了提高效率，把1和2放到一个循环中，同时从左往右和从右往左查找。当最高的山峰相同时就可以退出循环
	
	4、不需要合并结果集，用两个结果集分别计算海水面积即可
	
'''

def calc_sea(mountains):
	# 构造有效山峰数组
	lefts = []
	rights = []
	length = len(mountains)

	for idx, val in enumerate(mountains):

		if idx == 0:
			posi_l = 0
			max_l = mountains[0]
			posi_r = length-1
			max_r = mountains[posi_r]
			lefts.append([posi_l, max_l])
			rights.append([posi_r, max_r])
			continue

		if mountains[idx] >= max_l:
			posi_l = idx
			max_l = mountains[idx]
			lefts.append([posi_l, max_l])

		if posi_l == posi_r:
			break

		if mountains[-idx-1] >= max_r:
			posi_r = length - 1 - idx
			max_r = mountains[posi_r]
			rights.insert (0, [posi_r, max_r])
#			rights.append([posi_r, max_r])

		if posi_l == posi_r:
			break

	print 'lefts ', lefts
	print 'rights', rights
	sea_area = _calc_sea(lefts)
	sea_area+= _calc_sea(rights)


def _calc_sea(values):
	sea = 0
	for idx in range(len(values)-1):
		a = values[idx]
		b = values[idx+1]
		aa = (b[0]-a[0]-1) * min(a[1], b[1])    # 这样计算，没考虑两个有效山峰中间的山峰占掉的体积
		print a,b,aa
		sea += aa
	return sea


'''
	思路:
	1、先找到有效的山峰（从第一个山峰作为有效山峰，只要后边的山峰不小于当前值，则它也是有效山峰，然后再用新的有效山峰做基准继续查找）
	2、这样查找，会导致最高山峰后续的山峰都被抛弃了，所以还需要从右往左在查找一次，取两次查找的交集
	3、为了提高效率，把1和2放到一个循环中，同时从左往右和从右往左查找。当最高的山峰相同时就可以退出循环

	4、不需要合并结果集，用两个结果集分别计算海水面积即可
	5、在查找有效山峰的时候，就记录有效山峰之间的山峰累计值。在找到有效山峰后，取两个有效山峰的总体积数，减去之前的累计值，就是这两个有效山峰之间的海水量

'''
def calc_sea1(mountains):
	# 构造有效山峰数组
	lefts = []
	rights = []
	length = len(mountains)
	seas = 0

	for idx, val in enumerate(mountains):
		print 'idx=', idx, 'val=', mountains[idx], mountains[0-1-idx]
		if idx == 0:
			posi_l = 0
			max_l = mountains[0]
			last_l = [posi_l, max_l, 0, 0]

			posi_r = length-1
			max_r = mountains[posi_r]
			last_r = [posi_r, max_r, 0, 0]

			lefts.append(last_l)
			rights.append(last_r)
			continue

		if mountains[idx] >= max_l:
			posi_l = idx
			max_l = mountains[idx]

			# 计算这一段的海水量
			aa = (posi_l-last_l[0]-1) * min(max_l, last_l[1]) - last_l[2]
			seas += aa
#			print 'left=', last_l, posi_l, max_l, aa

			last_l = [posi_l, max_l, 0, aa]
			lefts.append(last_l)
		else:
			last_l[2] += mountains[idx]

		if posi_l == posi_r:
			break

		if mountains[-idx-1] >= max_r:
			posi_r = length - 1 - idx
			max_r = mountains[posi_r]

			# 计算这一段的海水量
			aa = (last_r[0] - posi_r - 1) * min(max_r, last_r[1]) - last_r[2]
			seas += aa
			print 'right=', last_r, posi_r, max_r, aa

			last_r = [posi_r, max_r, 0, aa]
			rights.insert (0, last_r)
		else:
			last_r[2] += mountains[-idx-1]

		if posi_l == posi_r:
			break

	print lefts
	print rights
	return seas, lefts, rights


def calc_sea_new_half(mountains):
	if len(mountains) == 1:
		return 0

	sea = 0
	high = 0
	for v in mountains:
		if high > v:
			sea += high - v
		else:
			high = v
	return sea


'''
	思路:
	1、找到最高的山峰，把整个数组分成两部分（第二部分翻转）
	2、分别计算两部分的蓄水量，求和
	3、calc_sea_new_half蓄水算法：
		因为最高的山峰一定是最后一个，那么只需要正向计算即可：
		从第一个山峰算起，下一个比它低，则差值为蓄水量。如果比它高，则本次没蓄水，比较高度以更高的为准往下计算
'''
def calc_sea_new(mountains):
	maxp = [0, 0]   # i,v
	for i,v in enumerate(mountains):
		if v > maxp[1]:
			maxp = [i, v]
	sea  = calc_sea_new_half(mountains[:maxp[0]+1])
	sea += calc_sea_new_half( list(reversed(mountains[maxp[0]:])) )
	return sea

if __name__ == "__main__":
	#mountain_array = input_mountain_value()
	mountain_array = [0,2,4,1,5,2,1,5,1,4,1,0, 2]
	print mountain_array

	print calc_sea_new(mountain_array)


'''
	用数值给出一组山峰，计算山峰之间可以存储的海曙数量
'''